package 左哥算法.ch10暴力递归;

import java.util.Arrays;


public class Ch04迷失古堡 {
    /**
     * 有n个宝箱，每个宝箱的价值为a，
     * 当开启当前宝箱时，下一个宝箱的值就会变为原来的0.5倍，不开当前宝箱时，下一个宝箱的值就会变为原来的1.5倍。
     * 问最多可以拿走的价值是多少
     */
    public static void main(String[] args) {
//        test();   //对数器
        double[] arr={1,1,1};
        System.out.println(diGui(arr.length, arr));
        System.out.println(dynamicPlanning(arr.length, arr));
    }

    //递归解
    public static double diGui(int n, double[] arr) {
        if (n < 1) {
            return 0;
        }
        if (n < 2) {
            return arr[0];
        }
        double open = fun(arr, 1, true) + arr[0];
        double close = fun(arr, 1, false);
        return Math.max(open, close);
    }
    /**
     * 获取当前节点是否被开时能拿的最大值
     * 上一个被开时：当前节点最大值为：当前节点*0.5+开当前节点后的下一个节点 与 不开当前节点后的下一个节点的最大值    两者的较大的一个
     * 上一个节点未被开：最大值为：当前节点*1.5+开当前节点后的下一个节点 与 不开当前节点后的下一个节点的最大值    两者的较大的一个
     */
    public static double fun(double[] arr, int n, boolean preOpen) {
        if (n == arr.length - 1) {    //最后一个无论如何都要开
            return preOpen ? arr[n] * 0.5 : arr[n] * 1.5;
        }
        double curr = preOpen ? arr[n] * 0.5 : arr[n] * 1.5;    //当前节点最大值
        double openCurr = fun(arr, n + 1, true) + curr;    //打开当前
        double closeCurr = fun(arr, n + 1, false);        //不要当前
        return Math.max(openCurr, closeCurr);
    }
    //改动态规划
    public static double dynamicPlanning(int n,double[] a) {
        if (n < 1) {
            return 0;
        }
        if (n < 2) {
            return a[0];
        }
        double[][] dp = new double[n][2];
        //basecase
        dp[n-1][0]=a[n-1]*0.5;
        dp[n-1][1]=a[n-1]*1.5;

        for (int i = dp.length - 2; i >= 1; i--) {
            dp[i][0]=Math.max(dp[i+1][0]+a[i]*0.5,dp[i+1][1]);        //上一个被开后能拿到的最大值
            dp[i][1]=Math.max(dp[i+1][0]+a[i]*1.5,dp[i+1][1]);       //上一个未被开能拿到的最大值
        }
        dp[0][0]=Math.max(dp[1][0]+a[0],dp[1][1]);
        return dp[0][0];
    }

    //对数器
    public static void test(){
        int count=10000;    //比较次数
        while (count-->0){
            int n = (int) (Math.random() * 30 ); //范围50，时间有点久，为了方便改为30
            double[] arr = new double[n];
            for (int i = 0;i<n; i++) {
                arr[i]=Math.random()*200;
            }
            long start=System.currentTimeMillis();
            double answer = dynamicPlanning(n, arr);
            long end=System.currentTimeMillis();
            long answerTime=end-start;//标准运行时间
            start=end;
            double fun = diGui(n, arr);
            end=System.currentTimeMillis();
            long funTime=end-start; //我的运行时长
            if (funTime>answerTime){    //运行可能超时的情况
                System.out.println("标准运行时长："+answerTime);
                System.out.println("自己的运行时长："+funTime);
            }
            if (answer!=fun){
                System.out.println(n);
                System.out.println(Arrays.toString(arr));
                System.out.println("预期输出："+answer);
                System.out.println("实际输出："+fun);
            }
        }
    }
}